package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/satisfiability-of-equality-equations/description/
 * @create 2025/9/23 20:02
 * @since JDK17
 */

public class Solution73 {
    int[] f = new int[26];
    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    void merge(int x, int y) {
        f[find(x)] = find(y);
    }


    public boolean equationsPossible(String[] equations) {
        for (int i = 0; i < 26; i++) {
            f[i] = i;
        }
        for (var equation : equations) {
            if (equation.charAt(1) == '=') {
                merge(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
            }
        }

        for (var equation : equations) {
            if (equation.charAt(1) == '!') {
                if (isSameSet(equation.charAt(0) - 'a', equation.charAt(3) - 'a')) {
                    return false;
                }
            }
        }

        return true;
    }
}
